class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size();
        // 把这个二维矩阵当作搜索二叉树看待
        // 把第一行最后一个元素当作二叉树的根
        // 它的左边都是比它小的，它的下边都是比它大的
        // 此方法确实很妙，时间复杂度最多就是O(m + n)，空间复杂度就是O(1)
        int i = 0, j = m - 1;
        while(i < n && j >= 0)
        {
            if(target < matrix[i][j])
                j--;
            else if(target > matrix[i][j])
                i++;
            else
                return true;
        }
        return false;
    }
};